#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<math.h>

//1:结构体实现（注释懒得改）
#define NAMESIZE 20                         //名称允许长度
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int STATUS;
typedef char NODETYPE[NAMESIZE];            //节点名称类型
typedef struct NODE
{
    NODETYPE name;
    int power;               //权值
}NODE;
typedef struct BROTHERNODE   //兄弟节点类型，表示兄弟关系
{
    NODE node;               //兄弟节点名称
    struct BROTHERNODE *next;//兄弟节点链接指针，链接其他兄弟
}BROTHERNODE,*BROTHER;       //重命名兄弟节点类型,BROTHER为指向BROTHERNODE的指针

typedef struct PARENTNODE     //双亲节点类型，表示子树树根节点
{
    NODE node;                //双亲节点名称              
    BROTHER children;         //所有子节点
}PARENT;                      //重命名双亲节点类型，PARENT为PARENTNODE的代名

typedef struct TREENODE       //树分支节点类型
{
    PARENT node;              //双亲节点，表示子树的树根节点
    struct TREENODE *next;    //双亲节点指针指向其他双亲节点
}TREENODE,*TREE;              //重命名树分支节点类型，TREE为指向TREENODE的指针

typedef struct BROTHERNODE *QUEUE;

typedef struct BROTHERNODE *PATH;   //路径类型

typedef struct PATHS                   //路径集合
{
    PATH path;
    struct PATHS *next;
}PATHS,*QUEUEPATHS;                    //路径栈【多条路径采用链式存储】

//2.1:兄弟节点关系的构建
BROTHER Add_A_Brother(BROTHER br,NODE node)        //Add_A_Brother把一个节点加入到兄弟节点群中
{
    BROTHER b,pb;                                  //兄弟节点
    b=(BROTHER)malloc(sizeof(struct BROTHERNODE)); //动态开辟一个兄弟节点
    //Set(b->node,node,node,SteValue);             //【下面两行是类型为str时的情况，其他类比】
    strcpy(b->node.name,node.name);
    b->node.power=node.power;
    b->next=NULL;
    if(br==NULL)                                    //没有兄弟节点的情况
    {
        br=b;                                       //node就是第一个兄弟
    }
    else                                            //有兄弟节点的情况
    {
        pb=br;                                      //node就是最后一个兄弟节点【值在b中，头插入】
        while(pb->next)   pb=pb->next;
        pb->next=b;
    }
    return br;                                      //返回兄弟节点【指针】
}

//2.2:双亲与子节点关系的构建
TREE Form_Pa_Ch(char *pa,BROTHER br)                 //将兄弟节点(所有子节点)链接到双亲节点中，构成一个子树
{
    TREE parent;
    parent=(TREE)malloc(sizeof(struct TREENODE));   //创建双亲节点
    //Set(parent->node.node,pa,Setvalue)
    strcpy(parent->node.node.name,pa);
    parent->node.node.power=-1;
    parent->next=NULL;
    parent->node.children=br;                       //兄弟节点与双亲节点构成子树
    return parent;                                  //返回带兄弟节点的双亲结点，即子树
}

//2.3:将带子节点的双亲节点加入到树中
TREE Add_A_Sub_Tree(TREE tree,TREE subtree) //将双亲结点加入到树中
{
    TREE t=tree;                        //临时树
    if(tree==NULL)                      //树不存在
    {
        tree=subtree;                   //带子节点的双亲节点即为树
    }
    else                                //树存在
    {
        while(t->next)  t=t->next;
        t->next=subtree;                //带子节点的双亲节点加入到树的最后
    }
    return tree;                        //返回树指针
}//tree是链式队列，通过上述程序实现子树subtree(双亲结点)进队列过程

//2.4:清除兄弟节点和树
BROTHER ClearBrothers(BROTHER br)  //回收兄弟节点空间
{
    BROTHER br1=br;                //临时兄弟变量
    while(br)                      //【遍历兄弟节点】
    {
        br1=br;
        br=br->next;               //【挨个变量赋给临时指针】
        free(br1);                 //回收单元
        return br;
    }
    return br;                     //返回NULL
}

//2.5:清空树并回收数据单元
TREE ClearTree(TREE tree)
{
    TREE tree1=tree;              //临时树
    while(tree)                   //【遍历双亲节点】
    {
        tree1=tree;
        tree=tree->next;          //【挨个变量赋给临时指针】
        free(tree1);              //回收单元
    }
    return tree;
}//在程序运行结束前需要动态回收动态开辟的数据单元
//以上两个程序实际上是出队列过程，只是没有返回值

//2.6:字符数值转换
//把字符串的字符'/'转换为转义字符'\0'(字符串结束标志)，故需要在字符串数组中存放多个节点名称(兄弟节点)的字符串
void CreateStr(char *brotherset)  //字符数组转换为多个字符串
{
    char *c=brotherset;           //临时字符串
    while(*c)
    {
        if(*c=='/')  *c='\0';     //插入字符串结束标志
        if(*c==',')  *c='\0';
        c++;
    }
    c++;
    *c='\0';                      //多一个结束标记
}

//2.7:字符数组建立兄弟关系
//把字符串数组中的多个兄弟节点节点名称建立成树的兄弟节点群(链表)
BROTHER CreateBrothers(BROTHER brothers,char *brotherset)   //若干个节点构成兄弟
{
    char *p=brotherset;                                     //多个节点，分隔符'/'
    char temp[20];
    NODE node;
    CreateStr(brotherset);                                  //变成多个字符串
    while(*p)
    {
        strcpy(node.name,p);
        p+=strlen(node.name)+1;
        strcpy(temp,p);
        sscanf(temp,"%d",&node.power);
        p+=strlen(temp)+1;
        brothers=Add_A_Brother(brothers,node);              //加入兄弟关系中
    }
    return brothers;                                        //返回兄弟节点链表
}

//2.8:根据树文件建立树
//树文件为txt文件，其记录格式为单数行为双亲节点，偶数行为子节点，用字符'/'分隔符分开
TREE CreateTree(TREE tree,char *filename)               //从文件创建树
{
    TREE subtree;
    BROTHER brothers;
    FILE *fp;
    char parent[200],brotherset[5000];
    fp=fopen(filename,"r");
    while(!feof(fp))                                     //文件中是否还存在树的节点名称
    {
        fscanf(fp,"%s",parent);                          //读入双亲节点
        fscanf(fp,"%s",brotherset);                      //读入若干兄弟节点(子节点)，分隔符'/'
        brothers=NULL;
        brothers=CreateBrothers(brothers,brotherset);    //构建双亲节点
        subtree=Form_Pa_Ch(parent,brothers);             //构建子树
        tree=Add_A_Sub_Tree(tree,subtree);                //树中加入子树
    }
    fclose(fp);                                          //关闭文件
    printf("[SUCCESS]建树成功\n");
    return tree;                                         //返回所建的树
}

//2.9:根据树文件找兄弟
void GetbrotherThroughFile(FILE *file,NODE n)               //从文件创建树
{
    STATUS flag=FALSE;
    char parent[200],brotherset[5000];
    while(!feof(file))                                     //文件中是否还存在树的节点名称
    {
        fscanf(file,"%s",parent);                          //读入双亲节点
        fscanf(file,"%s",brotherset);                      //读入若干兄弟节点(子节点)，分隔符'/'
        char *p=brotherset;
        char temp[20];
        CreateStr(brotherset);
        while(*p)
        {
            if(strcmp(p,n.name)!=0)
            {
                strcpy(temp,p);
                p+=strlen(temp)+1;
            }
            else if(strcmp(p,n.name)==0)
            {
                p=brotherset;
                flag=TRUE;
                printf("[SUCCESS]根据文件找兄弟\n");
                printf("[OUTPUT]结果如下:\n");
                while(*p)
                {
                    strcpy(temp,p);
                    p+=strlen(temp)+1;
                    printf("Node=%s",temp);
                    printf(",Power=");
                    strcpy(temp,p);
                    p+=strlen(temp)+1;
                    printf("%s\n",temp);
                }
                break;
            }
        }
    }
    if(flag==FALSE) printf("[UNSUCCESS]根据文件找兄弟");
}


//3.1:遍历孩子链表
STATUS ThroughBrothers(BROTHER children,char target[])   //节点集复制
{
    BROTHER nownode=children;
    while(nownode)
    {
        if(strcmp(nownode->node.name,target)!=0)
        {
            nownode=nownode->next;
        }
        else if(strcmp(nownode->node.name,target)==0)
        {
            return TRUE;
        }
    }
    return FALSE;
}

//3.2:根据树找兄弟
void GetBrothersFromTree(TREE tree,NODE n)                      
{                                                   //在tree中判断节点end是否在以节点start为根的子树中
    BROTHER children;                               //子节点集
    STATUS flag=FALSE;                              //节点在子树中标识，FALSE表示不存在，默认值
    while(tree)                                     //堆栈不为空
    {
        flag=ThroughBrothers(tree->node.children,n.name);
        if(flag==FALSE)  tree=tree->next;
        else if (flag=TRUE)
        {
            children=tree->node.children;
            printf("[SUCCESS]根据树找兄弟\n");
            printf("[OUTPUT]结果如下:\n");
            while(children)
            {
                printf("Node=%s",children->node.name);
                printf(",Power=");
                printf("%d\n",children->node.power);
                children=children->next;
            }
        }
        if(flag==TRUE)    break;
    }
    if(flag=FALSE)  printf("[UNSUCCESS]根据树找兄弟");
}

//4.1:复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
BROTHER CopyBrothers(BROTHER children)                       //节点集复制
{
    BROTHER copynode,lastnode,head=NULL;                     //没有子节点
    while(children)
    {
        copynode=(BROTHER)malloc(sizeof(struct BROTHERNODE));
        //Set(copynode->node,cildren->node,SetValue);
        strcpy(copynode->node.name,children->node.name);               //复制节点
        copynode->node.power=children->node.power;
        copynode->next=NULL;
        if(head==NULL)
        {
            head=copynode;                                   //第1个节点
        }
        else
        {
            lastnode->next=copynode;                         //非第1个节点：建立链接，复制子节点集
        }
        lastnode=copynode;
        children=children->next;                             //下一个子节点
    }
    copynode=head;                                           //返回头节点指针
}

//4.2:扩展节点集
//根据树结构从双亲节点中找到所有孩子节点(兄弟节点)，并复制所有孩子节点，最后返回所有复制结果的头指针
BROTHER ExpandNodes(TREE tree,NODE pa)              //由节点获取所有子节点
{
    int flag=0;
    BROTHER children=NULL;                          //孩子节点
    TREE t=tree,p;                                    //树
    while(t)                                        //节点不为空
    {
        //if(Equal(t->node.node,pa,EqualFun)==0)
        if(strcmp(t->node.node.name,pa.name)==0)              //找到分支节点
        {
            children=CopyBrothers(t->node.children);
            break;
        }
        t=t->next;
    }
    return children;
}

//4.3:所有节点进队
//将所有节点进栈并返回堆栈指针
void PushChildren(QUEUE* front,QUEUE* rear,BROTHER children)//所有节点进栈
{
    QUEUE head=children;
    if(*front==NULL)
    {
        *front=head;
        QUEUE p=*front;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        *rear=p;
        p=NULL;
        free(p);  
    }
    else if(*front!=NULL)
    {
        QUEUE p=*rear;
        (*rear)->next=head;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        *rear=p; 
        p=NULL;
        free(p);                  
    } 
}

//4.4:出队与回收队栈
QUEUE Pop_A_Child(QUEUE front,NODE child)  //出栈
{
    QUEUE p=front;
    if(p!=NULL)
    {
        strcpy(child.name,p->node.name);
        child.power=p->node.power;
        p=p->next;
        front=p;
    }
    return front;
    
}

QUEUE ClearQueue(QUEUE rear)              //回收栈空间
{
    rear=(QUEUE)ClearBrothers((BROTHER)rear);   //清除所有节点，得到空指针
    return rear;                                //返回空指针
}

//5.1:节点加入路径
PATH Add_A_Node_To_Path(NODE node,PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p=(BROTHER)malloc(sizeof(struct BROTHERNODE));
    //Set(p->node,node,SetValue)
    strcpy(p->node.name,node.name);           //等价，赋值
    if(path==NULL)                            //第1个节点
    {
        p->next=NULL;
    }
    else                                      //非第1个节点
    {
        p->next=path;                         //加入到路径头部
    }
    path=p;                                   //路径倒序加入
    return path;                              //返回路径头部
}

//5.2:复制路径与路径集合
PATH CopyPath(PATH path)                         //复制一条路径，返回新路径
{
    PATH tempath;
    tempath=(PATH)CopyBrothers((BROTHER)path);   //路径与兄弟节点集合相同、
    return tempath;
}

PATHS* CopyPaths(struct PATHS *paths)            //复制路径集合
{
    PATHS *copynode,*lastnode,*head=NULL;
    while(paths)                                 //路径集合不为空
    {
        copynode=(PATHS *)malloc(sizeof(PATHS)); //路径节点
        copynode->path=CopyPath(paths->path);    //复制一条路径
        copynode->next=NULL;                     //复制路径初始化
        if(head==NULL)                           //第1条路径
        {
            head=copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next=copynode;
        }
        lastnode=copynode;                        //加入路径集合
        paths=paths->next;
    }
    return head;
}

//5.3:路径倒序与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num=0,i;
    NODE *nodes;
    PATH p=path;
    while(p)                                //统计路径节点的个数
    {
        p=p->next;
        num++;
    }
    nodes=(NODE *)malloc(num*sizeof(NODE)); //开辟一维数组
    for(i=0,p=path;p;p=p->next,i++)         //读取路径节点置于数组中
    {
        //Set(nodes[i],p->node,SetValue);
        strcpy(nodes[i].name,p->node.name);
    }
    for(i=num-1,p=path;p;p=p->next,i--)     //数组数据倒序置于路径中
    {
        //Set(p->node,nodes[i],SetValue);
        strcpy(p->node.name,nodes[i].name);
    }
    free(nodes);                            //回收数组空间
}

void PriPath(PATH path)                     //显示路径
{
    while(path!=NULL)
    {
        if(path->next->node.name!=NULL)  printf("%s->",path->node.name);
        else                             printf("%s",path->node.name);
        path=path->next;
    }
    printf("\n");
    //priBrothers((BROTHER)path);             //路径与兄弟节点集合形式相同
}

//5.4:路径加入路径集合
PATHS* Add_A_Path_To_Paths(PATH path,PATHS* paths)//路径加入到路径集合中
{
    PATH copypath;
    PATHS *ps=NULL,*p;
    if(path==NULL)   return paths;                //没有路径
    copypath=CopyPath(path);                      //复制路径
    ps=(PATHS *)malloc(sizeof(PATHS));            //开辟路径集合节点
    ps->path=copypath;                            //复制的路径置入
    ps->next=NULL;
    if(paths==NULL)                               //路径集合为空
    {
        paths=ps;
    }
    else                                          //路径集合为非空，新路径节点放置最后
    {
        p=paths;
        while(p->next) p=p->next;
        p->next=ps;
    }
    return paths;
}

//5.5:节点集合与路径形成路径集合
PATH FormPathsFromNodes(BROTHER brothers,PATH path,PATHS* *paths)
//将每个节点均加入到路径中形成一条路径，最终形成多条路径
{
    PATH tempath=path;
    while(brothers)                                         //存在节点
    {
        tempath=Add_A_Node_To_Path(brothers->node,tempath);   //节点加入路径
        *paths=Add_A_Path_To_Paths(tempath,*paths);           //新路径加入路径集合                                  //MODE:
        brothers=brothers->next;                              //下一个节点
    }
    return tempath;                                           //返回路径集合
}

//5.6:回收路径和路径集合空间
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path=(PATH)ClearBrothers((BROTHER)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS* ClearPaths(PATHS* paths)               //回收路径集合空间
{
    PATHS *paths1=paths;
    while(paths&&paths1)                              //所有路径
    {
        paths1=paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths=paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//5.7:路径进栈与所有路径进栈
QUEUEPATHS Push_A_Path(QUEUEPATHS front,PATH path)     //一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    QUEUEPATHS st;
    tempath=CopyPath(path);                            //复制节点
    st=(PATHS *)malloc(sizeof(PATHS));                 //路径节点
    st->path=tempath;                                  //置路径于队中
    if(front==NULL)                                   //第1条路径
    {
        st->next=front;
    }
    else                                               //非第1条路径，已有路径
    {
        st->next=front;
    }
    front=st;
    return front;
}

void PushPaths(QUEUEPATHS* front,QUEUEPATHS *rear,PATHS *paths)  //所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS *head;
    QUEUEPATHS p;
    head=CopyPaths(paths);                                    //复制路径集合
    if(*front==NULL)
    {
        *front=head;
        p=*front;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        *rear=p;
    }
    else if(*front!=NULL)
    {
        p=*rear;
        (*rear)->next=head;
        while(p->next!=NULL)
        {
            p=p->next;
        }
        *rear=p;
    }
    p=NULL;
    head=NULL;
    free(p);
    free(head);
}

//5.8:出栈与节点
QUEUEPATHS Pop_A_Node(QUEUEPATHS front,NODE *node,PATH *path)  //出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    QUEUEPATHS p=front;
    PATH tempath;
    if(p!=NULL)
    {
        tempath=p->path;                                //一条路径
        //Set(node,tempath->node,SetValue);
        strcpy(node->name,tempath->node.name);           //获取节点
        *path=CopyPath(tempath);                        //获取路径
        front=p->next;                                  //栈顶变化
        free(p);                                        //删除路径 
    }
    return front;                                       //返回栈顶
}

//5.9:回收栈顶
QUEUEPATHS ClearStackPATHS(QUEUEPATHS front)          //回收堆栈数据空间，复用了路径集合回收函数
{
    front=(QUEUEPATHS)ClearPaths((PATHS *)front);  //堆栈与路径的集合形式相同，复用函数              
    return front;
}

//5.10:路径求解
STATUS SearchPath(TREE tree,NODE start,NODE end,PATH *path)//判断节点是否在树种，并求取路径
{
    int count=0;
    NODE node;                                             //树节点名称
    BROTHER children;                                      //树孩子节点
    QUEUEPATHS front,rear,temp;
    STATUS flag=FALSE;                                     //堆栈是否为空的标识
    PATH tempath=NULL;                                     //临时路径
    PATH BFSpath=NULL;
    PATHS *paths=NULL;                                     //路径集合
    if(tree==NULL)  return flag;                           //树为空
    tempath=Add_A_Node_To_Path(start,tempath);             //形成路径
    BFSpath=Add_A_Node_To_Path(start,BFSpath);
    front=Push_A_Path(front,tempath);                      //路径进栈
    front->next=NULL;
    rear=front;
    while(front)                                           //堆栈不为空继续搜索
    {
        front=Pop_A_Node(front,&node,&tempath);             //出栈获取树节点和路径
        if(strcmp(end.name,node.name)==0)                  //判断是否为所求目标节点
        {
            flag=TRUE;                                     //修正标识
            *path=(PATH)CopyPath(tempath);                 //获取路径
            break;
        }
        children=ExpandNodes(tree,node);                   //获取下一次所有节点
        if(children!=NULL)
        {
            tempath=FormPathsFromNodes(children,BFSpath,&paths);  //形成路径集合
            while(children)
            {
                BFSpath=Add_A_Node_To_Path(children->node,BFSpath);
                printf("[PROCESS]");
                PriPath(BFSpath); 
                children=children->next; 
            }
            PushPaths(&front,&rear,paths);                        //所有路径进栈
            paths=ClearPaths(paths);                              //清除所有路径
        }
    }
    ClearStackPATHS(front);                                //清除堆栈
    return flag;                                           //获得路径标识
}

int main()
{
    NODE search;
    printf("[INFO]以下是第二题：\n");
    printf("[INPUT]The Search Node:");
    scanf("%s",search.name);
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Test\\Test.txt";//图文件
    FILE *fp=fopen(filename,"r");
    GetbrotherThroughFile(fp,search);
    fclose(fp);

    printf("\n[INFO]以下是第三题：\n");
    STATUS flag;                                                   //节点是否在图中
    TREE tree=NULL;    
    tree=CreateTree(tree,filename);                                  //建立图存储结构
    
    printf("\n[INFO]以下是第四题：\n");
    printf("[INPUT]The Search Node:");
    scanf("%s",search.name);
    GetBrothersFromTree(tree,search);

    printf("\n[INFO]以下是第五题：\n");
    QUEUE front=NULL;                                               //路径堆栈
    NODE start,end;                                                 //树开始节点名称和目标节点名称
    PATH path=NULL;                                                 //求得的路径
    printf("[INPUT]The Start Node:");
    scanf("%s",start.name);                                              //输入子树根节点名
    printf("[INPUT]The End Node:");
    scanf("%s",end.name);                                                //输入目标节点名称
    flag=SearchPath(tree,start,end,&path);                          //节点start到节点end的路径
    printf("[OUTPUT]Search %s from %s,Status=%d\n",end,start,flag);
    printf("[OUTPUT]Path=");
    RevPath(path);                                                  //路径倒序
    PriPath(path);                                                  //显示路径
    printf("=============热烈庆祝短学期结束============\n");
    ClearPath(path);
    ClearTree(tree);                                                //清空树结构空间
}